#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2018/9/27 09:41
# @Author  : yangdy
# @Email   : yangdy@egu360.com
# @File    : 中级-搜索旋转排序数组.py
# @Software: PyCharm


class Solution:
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        if not nums:
            return -1
        k = 0
        l = len(nums)
        # if l == 1:
        #     return 0 if nums[0] == target else -1
        j = l - 1
        t = nums[j]
        while k < j:
            h = (k + j) // 2
            x = nums[h]
            if x > t:
                k = h + 1
            else:
                j = h

        def find(a, ii, jj, tt):
            if ii > jj:
                return -1
            while ii < jj:
                hh = (ii+jj)//2
                xx = a[hh]
                if xx == tt:
                    return hh
                elif xx > tt:
                    jj = hh-1
                else:
                    ii = hh+1
            return ii if a[ii] == tt else -1

        if k > 0 and target >= nums[0]:
            ans = find(nums, 0, k-1, target)
        else:
            ans = find(nums, k, l-1, target)
        if 0 <= ans < l and nums[ans] == target:
            return ans
        else:
            return -1


def main():
    # nums = [4, 5, 6, 7, 0, 1, 2]
    # target = 0
    # nums = [4, 5, 6, 7, 0, 1, 2]
    # target = 3
    # nums = [1, 3]
    # target = 3
    # nums = [5, 1, 3]
    # target = 1
    # nums = [2, 4, 6, 9]
    # target = 4
    # nums = [1]
    # target = 1
    # nums = [1, 3]
    # target = 1
    nums = [3, 1]
    target = 1
    print(nums, target)
    solve = Solution()
    ans = solve.search(nums, target)
    print('ans:', ans)


if __name__ == '__main__':
    main()
